// functional standard header
#pragma once
#ifndef _FUNCTIONAL_
#define _FUNCTIONAL_
#ifndef RC_INVOKED
#include <exception>
#include <tuple>
#include <typeinfo>
#include <xmemory0>
#include <xstddef>
#if _HAS_CXX17
#include <memory>
#include <unordered_map>
#endif // _HAS_CXX17

#pragma pack(push, _CRT_PACKING)
#pragma warning(push, _STL_WARNING_LEVEL)
#pragma warning(disable : _STL_DISABLED_WARNINGS)
_STL_DISABLE_CLANG_WARNINGS
#pragma push_macro("new")
#undef new

_STD_BEGIN
// STRUCT TEMPLATE plus
// defined in <xstddef>

// STRUCT TEMPLATE minus
// defined in <xstddef>

// STRUCT TEMPLATE multiplies
// defined in <xstddef>

// STRUCT TEMPLATE divides
template <class _Ty = void>
struct divides { // functor for operator/
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty first_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty second_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty result_type;

    constexpr _Ty operator()(const _Ty& _Left, const _Ty& _Right) const { // apply operator/ to operands
        return _Left / _Right;
    }
};

// STRUCT TEMPLATE modulus
template <class _Ty = void>
struct modulus { // functor for operator%
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty first_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty second_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty result_type;

    constexpr _Ty operator()(const _Ty& _Left, const _Ty& _Right) const { // apply operator% to operands
        return _Left % _Right;
    }
};

// STRUCT TEMPLATE negate
template <class _Ty = void>
struct negate { // functor for unary operator-
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty result_type;

    constexpr _Ty operator()(const _Ty& _Left) const { // apply operator- to operand
        return -_Left;
    }
};

// STRUCT TEMPLATE equal_to
// defined in <xstddef>

// STRUCT TEMPLATE not_equal_to
// defined in <xstddef>

// STRUCT TEMPLATE greater
// defined in <xstddef>

// STRUCT TEMPLATE less
// defined in <xstddef>

// STRUCT TEMPLATE greater_equal
// defined in <xstddef>

// STRUCT TEMPLATE less_equal
// defined in <xstddef>

// STRUCT TEMPLATE logical_and
template <class _Ty = void>
struct logical_and { // functor for operator&&
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty first_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty second_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef bool result_type;

    constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const { // apply operator&& to operands
        return _Left && _Right;
    }
};

// STRUCT TEMPLATE logical_or
template <class _Ty = void>
struct logical_or { // functor for operator||
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty first_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty second_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef bool result_type;

    constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const { // apply operator|| to operands
        return _Left || _Right;
    }
};

// STRUCT TEMPLATE logical_not
template <class _Ty = void>
struct logical_not { // functor for unary operator!
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef bool result_type;

    constexpr bool operator()(const _Ty& _Left) const { // apply operator! to operand
        return !_Left;
    }
};

// STRUCT TEMPLATE bit_and
template <class _Ty = void>
struct bit_and { // functor for operator&
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty first_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty second_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty result_type;

    constexpr _Ty operator()(const _Ty& _Left, const _Ty& _Right) const { // apply operator& to operands
        return _Left & _Right;
    }
};

// STRUCT TEMPLATE bit_or
template <class _Ty = void>
struct bit_or { // functor for operator|
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty first_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty second_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty result_type;

    constexpr _Ty operator()(const _Ty& _Left, const _Ty& _Right) const { // apply operator| to operands
        return _Left | _Right;
    }
};

// STRUCT TEMPLATE bit_xor
template <class _Ty = void>
struct bit_xor { // functor for operator^
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty first_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty second_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty result_type;

    constexpr _Ty operator()(const _Ty& _Left, const _Ty& _Right) const { // apply operator^ to operands
        return _Left ^ _Right;
    }
};

// STRUCT TEMPLATE bit_not
template <class _Ty = void>
struct bit_not { // functor for unary operator~
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty result_type;

    constexpr _Ty operator()(const _Ty& _Left) const { // apply operator~ to operand
        return ~_Left;
    }
};

// STRUCT TEMPLATE SPECIALIZATION plus
// defined in <xstddef>

// STRUCT TEMPLATE SPECIALIZATION minus
// defined in <xstddef>

// STRUCT TEMPLATE SPECIALIZATION multiplies
// defined in <xstddef>

// STRUCT TEMPLATE SPECIALIZATION divides
template <>
struct divides<void> { // transparent functor for operator/
    using is_transparent = int;

    template <class _Ty1, class _Ty2>
    constexpr auto operator()(_Ty1&& _Left, _Ty2&& _Right) const -> decltype(
        _STD forward<_Ty1>(_Left) / _STD forward<_Ty2>(_Right)) { // transparently apply operator/ to operands
        return _STD forward<_Ty1>(_Left) / _STD forward<_Ty2>(_Right);
    }
};

// STRUCT TEMPLATE SPECIALIZATION modulus
template <>
struct modulus<void> { // transparent functor for operator%
    using is_transparent = int;

    template <class _Ty1, class _Ty2>
    constexpr auto operator()(_Ty1&& _Left, _Ty2&& _Right) const -> decltype(
        _STD forward<_Ty1>(_Left) % _STD forward<_Ty2>(_Right)) { // transparently apply operator% to operands
        return _STD forward<_Ty1>(_Left) % _STD forward<_Ty2>(_Right);
    }
};

// STRUCT TEMPLATE SPECIALIZATION negate
template <>
struct negate<void> { // transparent functor for unary operator-
    using is_transparent = int;

    template <class _Ty>
    constexpr auto operator()(_Ty&& _Left) const
        -> decltype(-_STD forward<_Ty>(_Left)) { // transparently apply operator- to operand
        return -_STD forward<_Ty>(_Left);
    }
};

// STRUCT TEMPLATE SPECIALIZATION equal_to
// defined in <xstddef>

// STRUCT TEMPLATE SPECIALIZATION not_equal_to
// defined in <xstddef>

// STRUCT TEMPLATE SPECIALIZATION greater
// defined in <xstddef>

// STRUCT TEMPLATE SPECIALIZATION less
// defined in <xstddef>

// STRUCT TEMPLATE SPECIALIZATION greater_equal
// defined in <xstddef>

// STRUCT TEMPLATE SPECIALIZATION less_equal
// defined in <xstddef>

// STRUCT TEMPLATE SPECIALIZATION logical_and
template <>
struct logical_and<void> { // transparent functor for operator&&
    using is_transparent = int;

    template <class _Ty1, class _Ty2>
    constexpr auto operator()(_Ty1&& _Left, _Ty2&& _Right) const -> decltype(
        _STD forward<_Ty1>(_Left) && _STD forward<_Ty2>(_Right)) { // transparently apply operator&& to operands
        return _STD forward<_Ty1>(_Left) && _STD forward<_Ty2>(_Right);
    }
};

// STRUCT TEMPLATE SPECIALIZATION logical_or
template <>
struct logical_or<void> { // transparent functor for operator||
    using is_transparent = int;

    template <class _Ty1, class _Ty2>
    constexpr auto operator()(_Ty1&& _Left, _Ty2&& _Right) const -> decltype(
        _STD forward<_Ty1>(_Left) || _STD forward<_Ty2>(_Right)) { // transparently apply operator|| to operands
        return _STD forward<_Ty1>(_Left) || _STD forward<_Ty2>(_Right);
    }
};

// STRUCT TEMPLATE SPECIALIZATION logical_not
template <>
struct logical_not<void> { // transparent functor for unary operator!
    using is_transparent = int;

    template <class _Ty>
    constexpr auto operator()(_Ty&& _Left) const
        -> decltype(!_STD forward<_Ty>(_Left)) { // transparently apply operator! to operand
        return !_STD forward<_Ty>(_Left);
    }
};

// STRUCT TEMPLATE SPECIALIZATION bit_and
template <>
struct bit_and<void> { // transparent functor for operator&
    using is_transparent = int;

    template <class _Ty1, class _Ty2>
    constexpr auto operator()(_Ty1&& _Left, _Ty2&& _Right) const -> decltype(
        _STD forward<_Ty1>(_Left) & _STD forward<_Ty2>(_Right)) { // transparently apply operator& to operands
        return _STD forward<_Ty1>(_Left) & _STD forward<_Ty2>(_Right);
    }
};

// STRUCT TEMPLATE SPECIALIZATION bit_or
template <>
struct bit_or<void> { // transparent functor for operator|
    using is_transparent = int;

    template <class _Ty1, class _Ty2>
    constexpr auto operator()(_Ty1&& _Left, _Ty2&& _Right) const -> decltype(
        _STD forward<_Ty1>(_Left) | _STD forward<_Ty2>(_Right)) { // transparently apply operator| to operands
        return _STD forward<_Ty1>(_Left) | _STD forward<_Ty2>(_Right);
    }
};

// STRUCT TEMPLATE SPECIALIZATION bit_xor
template <>
struct bit_xor<void> { // transparent functor for operator^
    using is_transparent = int;

    template <class _Ty1, class _Ty2>
    constexpr auto operator()(_Ty1&& _Left, _Ty2&& _Right) const -> decltype(
        _STD forward<_Ty1>(_Left) ^ _STD forward<_Ty2>(_Right)) { // transparently apply operator^ to operands
        return _STD forward<_Ty1>(_Left) ^ _STD forward<_Ty2>(_Right);
    }
};

// STRUCT TEMPLATE SPECIALIZATION bit_not
template <>
struct bit_not<void> { // transparent functor for unary operator~
    using is_transparent = int;

    template <class _Ty>
    constexpr auto operator()(_Ty&& _Left) const
        -> decltype(~_STD forward<_Ty>(_Left)) { // transparently apply operator~ to operand
        return ~_STD forward<_Ty>(_Left);
    }
};

#pragma warning(push)
#pragma warning(disable : 4996) // was declared deprecated
// CLASS TEMPLATE unary_negate
template <class _Fn>
class _CXX17_DEPRECATE_NEGATORS unary_negate { // functor adapter !_Func(left)
public:
    using argument_type = typename _Fn::argument_type;
    using result_type   = bool;

    constexpr explicit unary_negate(const _Fn& _Func) : _Functor(_Func) { // construct from functor
    }

    constexpr bool operator()(const argument_type& _Left) const { // apply functor to operand
        return !_Functor(_Left);
    }

private:
    _Fn _Functor; // the functor to apply
};

// FUNCTION TEMPLATE not1
template <class _Fn>
_NODISCARD _CXX17_DEPRECATE_NEGATORS constexpr unary_negate<_Fn> not1(
    const _Fn& _Func) { // return a unary_negate functor adapter
    return unary_negate<_Fn>(_Func);
}

// CLASS TEMPLATE binary_negate
template <class _Fn>
class _CXX17_DEPRECATE_NEGATORS binary_negate { // functor adapter !_Func(left, right)
public:
    using first_argument_type  = typename _Fn::first_argument_type;
    using second_argument_type = typename _Fn::second_argument_type;
    using result_type          = bool;

    constexpr explicit binary_negate(const _Fn& _Func) : _Functor(_Func) { // construct from functor
    }

    constexpr bool operator()(const first_argument_type& _Left,
        const second_argument_type& _Right) const { // apply functor to operands
        return !_Functor(_Left, _Right);
    }

private:
    _Fn _Functor; // the functor to apply
};

// FUNCTION TEMPLATE not2
template <class _Fn>
_NODISCARD _CXX17_DEPRECATE_NEGATORS constexpr binary_negate<_Fn> not2(
    const _Fn& _Func) { // return a binary_negate functor adapter
    return binary_negate<_Fn>(_Func);
}
#pragma warning(pop)

#if _HAS_AUTO_PTR_ETC
#pragma warning(push)
#pragma warning(disable : 4996) // was declared deprecated
// CLASS TEMPLATE binder1st
template <class _Fn>
class binder1st : public unary_function<typename _Fn::second_argument_type,
                      typename _Fn::result_type> { // functor adapter _Func(stored, right)
public:
    using _Base         = unary_function<typename _Fn::second_argument_type, typename _Fn::result_type>;
    using argument_type = typename _Base::argument_type;
    using result_type   = typename _Base::result_type;

    binder1st(const _Fn& _Func, const typename _Fn::first_argument_type& _Left)
        : op(_Func), value(_Left) { // construct from functor and left operand
    }

    result_type operator()(const argument_type& _Right) const { // apply functor to operands
        return op(value, _Right);
    }

    result_type operator()(argument_type& _Right) const { // apply functor to operands
        return op(value, _Right);
    }

protected:
    _Fn op; // the functor to apply
    typename _Fn::first_argument_type value; // the left operand
};

// FUNCTION TEMPLATE bind1st
template <class _Fn, class _Ty>
_NODISCARD inline binder1st<_Fn> bind1st(const _Fn& _Func, const _Ty& _Left) { // return a binder1st functor adapter
    typename _Fn::first_argument_type _Val(_Left);
    return binder1st<_Fn>(_Func, _Val);
}

// CLASS TEMPLATE binder2nd
template <class _Fn>
class binder2nd : public unary_function<typename _Fn::first_argument_type,
                      typename _Fn::result_type> { // functor adapter _Func(left, stored)
public:
    using _Base         = unary_function<typename _Fn::first_argument_type, typename _Fn::result_type>;
    using argument_type = typename _Base::argument_type;
    using result_type   = typename _Base::result_type;

    binder2nd(const _Fn& _Func, const typename _Fn::second_argument_type& _Right)
        : op(_Func), value(_Right) { // construct from functor and right operand
    }

    result_type operator()(const argument_type& _Left) const { // apply functor to operands
        return op(_Left, value);
    }

    result_type operator()(argument_type& _Left) const { // apply functor to operands
        return op(_Left, value);
    }

protected:
    _Fn op; // the functor to apply
    typename _Fn::second_argument_type value; // the right operand
};

// FUNCTION TEMPLATE bind2nd
template <class _Fn, class _Ty>
_NODISCARD inline binder2nd<_Fn> bind2nd(const _Fn& _Func, const _Ty& _Right) { // return a binder2nd functor adapter
    typename _Fn::second_argument_type _Val(_Right);
    return binder2nd<_Fn>(_Func, _Val);
}
#pragma warning(pop)

// CLASS TEMPLATE pointer_to_unary_function
template <class _Arg, class _Result, class _Fn = _Result (*)(_Arg)>
class pointer_to_unary_function : public unary_function<_Arg, _Result> { // functor adapter (*pfunc)(left)
public:
    explicit pointer_to_unary_function(_Fn _Left) : _Pfun(_Left) { // construct from pointer
    }

    _Result operator()(_Arg _Left) const { // call function with operand
        return _Pfun(_Left);
    }

protected:
    _Fn _Pfun; // the function pointer
};

// CLASS TEMPLATE pointer_to_binary_function
template <class _Arg1, class _Arg2, class _Result, class _Fn = _Result (*)(_Arg1, _Arg2)>
class pointer_to_binary_function
    : public binary_function<_Arg1, _Arg2, _Result> { // functor adapter (*pfunc)(left, right)
public:
    explicit pointer_to_binary_function(_Fn _Left) : _Pfun(_Left) { // construct from pointer
    }

    _Result operator()(_Arg1 _Left, _Arg2 _Right) const { // call function with operands
        return _Pfun(_Left, _Right);
    }

protected:
    _Fn _Pfun; // the function pointer
};

// FUNCTION TEMPLATE ptr_fun
#define _PTR_FUN(CALL_OPT, X1, X2, X3)                                                                             \
    template <class _Arg, class _Result>                                                                           \
    _NODISCARD inline pointer_to_unary_function<_Arg, _Result, _Result(CALL_OPT*)(_Arg)> ptr_fun(                  \
        _Result(CALL_OPT* _Left)(_Arg)) { /* return pointer_to_unary_function functor adapter */                   \
        return pointer_to_unary_function<_Arg, _Result, _Result(CALL_OPT*)(_Arg)>(_Left);                          \
    }                                                                                                              \
    template <class _Arg1, class _Arg2, class _Result>                                                             \
    _NODISCARD inline pointer_to_binary_function<_Arg1, _Arg2, _Result, _Result(CALL_OPT*)(_Arg1, _Arg2)> ptr_fun( \
        _Result(CALL_OPT* _Left)(_Arg1, _Arg2)) { /* return pointer_to_binary_function functor adapter */          \
        return pointer_to_binary_function<_Arg1, _Arg2, _Result, _Result(CALL_OPT*)(_Arg1, _Arg2)>(_Left);         \
    }

_NON_MEMBER_CALL(_PTR_FUN, X1, X2, X3)
#undef _PTR_FUN

// CLASS TEMPLATE mem_fun_t
template <class _Result, class _Ty>
class mem_fun_t : public unary_function<_Ty*, _Result> { // functor adapter (*p->*pfunc)(), non-const *pfunc
public:
    explicit mem_fun_t(_Result (_Ty::*_Pm)()) : _Pmemfun(_Pm) { // construct from pointer
    }

    _Result operator()(_Ty* _Pleft) const { // call function
        return (_Pleft->*_Pmemfun)();
    }

private:
    _Result (_Ty::*_Pmemfun)(); // the member function pointer
};

// CLASS TEMPLATE mem_fun1_t
template <class _Result, class _Ty, class _Arg>
class mem_fun1_t : public binary_function<_Ty*, _Arg, _Result> { // functor adapter (*p->*pfunc)(val), non-const *pfunc
public:
    explicit mem_fun1_t(_Result (_Ty::*_Pm)(_Arg)) : _Pmemfun(_Pm) { // construct from pointer
    }

    _Result operator()(_Ty* _Pleft, _Arg _Right) const { // call function with operand
        return (_Pleft->*_Pmemfun)(_Right);
    }

private:
    _Result (_Ty::*_Pmemfun)(_Arg); // the member function pointer
};

// CLASS TEMPLATE const_mem_fun_t
template <class _Result, class _Ty>
class const_mem_fun_t : public unary_function<const _Ty*, _Result> { // functor adapter (*p->*pfunc)(), const *pfunc
public:
    explicit const_mem_fun_t(_Result (_Ty::*_Pm)() const) : _Pmemfun(_Pm) { // construct from pointer
    }

    _Result operator()(const _Ty* _Pleft) const { // call function
        return (_Pleft->*_Pmemfun)();
    }

private:
    _Result (_Ty::*_Pmemfun)() const; // the member function pointer
};

// CLASS TEMPLATE const_mem_fun1_t
template <class _Result, class _Ty, class _Arg>
class const_mem_fun1_t
    : public binary_function<const _Ty*, _Arg, _Result> { // functor adapter (*p->*pfunc)(val), const *pfunc
public:
    explicit const_mem_fun1_t(_Result (_Ty::*_Pm)(_Arg) const) : _Pmemfun(_Pm) { // construct from pointer
    }

    _Result operator()(const _Ty* _Pleft, _Arg _Right) const { // call function with operand
        return (_Pleft->*_Pmemfun)(_Right);
    }

private:
    _Result (_Ty::*_Pmemfun)(_Arg) const; // the member function pointer
};

// FUNCTION TEMPLATE mem_fun
template <class _Result, class _Ty>
_NODISCARD inline mem_fun_t<_Result, _Ty> mem_fun(_Result (_Ty::*_Pm)()) { // return a mem_fun_t functor adapter
    return mem_fun_t<_Result, _Ty>(_Pm);
}

template <class _Result, class _Ty, class _Arg>
_NODISCARD inline mem_fun1_t<_Result, _Ty, _Arg> mem_fun(
    _Result (_Ty::*_Pm)(_Arg)) { // return a mem_fun1_t functor adapter
    return mem_fun1_t<_Result, _Ty, _Arg>(_Pm);
}

template <class _Result, class _Ty>
_NODISCARD inline const_mem_fun_t<_Result, _Ty> mem_fun(
    _Result (_Ty::*_Pm)() const) { // return a const_mem_fun_t functor adapter
    return const_mem_fun_t<_Result, _Ty>(_Pm);
}

template <class _Result, class _Ty, class _Arg>
_NODISCARD inline const_mem_fun1_t<_Result, _Ty, _Arg> mem_fun(
    _Result (_Ty::*_Pm)(_Arg) const) { // return a const_mem_fun1_t functor adapter
    return const_mem_fun1_t<_Result, _Ty, _Arg>(_Pm);
}

// CLASS TEMPLATE mem_fun_ref_t
template <class _Result, class _Ty>
class mem_fun_ref_t : public unary_function<_Ty, _Result> { // functor adapter (*left.*pfunc)(), non-const *pfunc
public:
    explicit mem_fun_ref_t(_Result (_Ty::*_Pm)()) : _Pmemfun(_Pm) { // construct from pointer
    }

    _Result operator()(_Ty& _Left) const { // call function
        return (_Left.*_Pmemfun)();
    }

private:
    _Result (_Ty::*_Pmemfun)(); // the member function pointer
};

// CLASS TEMPLATE mem_fun1_ref_t
template <class _Result, class _Ty, class _Arg>
class mem_fun1_ref_t
    : public binary_function<_Ty, _Arg, _Result> { // functor adapter (*left.*pfunc)(val), non-const *pfunc
public:
    explicit mem_fun1_ref_t(_Result (_Ty::*_Pm)(_Arg)) : _Pmemfun(_Pm) { // construct from pointer
    }

    _Result operator()(_Ty& _Left, _Arg _Right) const { // call function with operand
        return (_Left.*_Pmemfun)(_Right);
    }

private:
    _Result (_Ty::*_Pmemfun)(_Arg); // the member function pointer
};

// CLASS TEMPLATE const_mem_fun_ref_t
template <class _Result, class _Ty>
class const_mem_fun_ref_t : public unary_function<_Ty, _Result> { // functor adapter (*left.*pfunc)(), const *pfunc
public:
    explicit const_mem_fun_ref_t(_Result (_Ty::*_Pm)() const) : _Pmemfun(_Pm) { // construct from pointer
    }

    _Result operator()(const _Ty& _Left) const { // call function
        return (_Left.*_Pmemfun)();
    }

private:
    _Result (_Ty::*_Pmemfun)() const; // the member function pointer
};

// CLASS TEMPLATE const_mem_fun1_ref_t
template <class _Result, class _Ty, class _Arg>
class const_mem_fun1_ref_t
    : public binary_function<_Ty, _Arg, _Result> { // functor adapter (*left.*pfunc)(val), const *pfunc
public:
    explicit const_mem_fun1_ref_t(_Result (_Ty::*_Pm)(_Arg) const) : _Pmemfun(_Pm) { // construct from pointer
    }

    _Result operator()(const _Ty& _Left, _Arg _Right) const { // call function with operand
        return (_Left.*_Pmemfun)(_Right);
    }

private:
    _Result (_Ty::*_Pmemfun)(_Arg) const; // the member function pointer
};

// FUNCTION TEMPLATE mem_fun_ref
template <class _Result, class _Ty>
_NODISCARD inline mem_fun_ref_t<_Result, _Ty> mem_fun_ref(
    _Result (_Ty::*_Pm)()) { // return a mem_fun_ref_t functor adapter
    return mem_fun_ref_t<_Result, _Ty>(_Pm);
}

template <class _Result, class _Ty, class _Arg>
_NODISCARD inline mem_fun1_ref_t<_Result, _Ty, _Arg> mem_fun_ref(
    _Result (_Ty::*_Pm)(_Arg)) { // return a mem_fun1_ref_t functor adapter
    return mem_fun1_ref_t<_Result, _Ty, _Arg>(_Pm);
}

template <class _Result, class _Ty>
_NODISCARD inline const_mem_fun_ref_t<_Result, _Ty> mem_fun_ref(
    _Result (_Ty::*_Pm)() const) { // return a const_mem_fun_ref_t functor adapter
    return const_mem_fun_ref_t<_Result, _Ty>(_Pm);
}

template <class _Result, class _Ty, class _Arg>
_NODISCARD inline const_mem_fun1_ref_t<_Result, _Ty, _Arg> mem_fun_ref(
    _Result (_Ty::*_Pm)(_Arg) const) { // return a const_mem_fun1_ref_t functor adapter
    return const_mem_fun1_ref_t<_Result, _Ty, _Arg>(_Pm);
}
#endif // _HAS_AUTO_PTR_ETC

// FUNCTION TEMPLATE mem_fn
template <class _Memptr>
class _Mem_fn : public _Weak_types<_Memptr>::type { // wrap a pointer to member function/data
private:
    _Memptr _Pm;

public:
    explicit _Mem_fn(_Memptr _Val) noexcept : _Pm(_Val) { // construct, storing a pointer to member function/data
    }

    template <class... _Types>
    auto operator()(_Types&&... _Args) const
        _NOEXCEPT_COND(noexcept(_STD invoke(_Pm, _STD forward<_Types>(_Args)...))) // strengthened
        -> decltype(_STD invoke(_Pm, _STD forward<_Types>(_Args)...)) { // invoke a pointer to member function/data
        return _STD invoke(_Pm, _STD forward<_Types>(_Args)...);
    }
};

template <class _Rx,
    class _Ty>
_NODISCARD inline _Mem_fn<_Rx _Ty::*> mem_fn(_Rx _Ty::*_Pm) noexcept { // wrap a pointer to member function/data
    return _Mem_fn<_Rx _Ty::*>(_Pm);
}

#if _HAS_CXX17
// CLASS TEMPLATE _Ebco_base
template <class _Ty,
    bool = is_empty_v<_Ty> && !is_final_v<_Ty>>
class _Ebco_base : private _Ty { // Empty Base Class Optimization, active
private:
    using _Mybase = _Ty; // for visualization

protected:
    template <class _Other, enable_if_t<!is_same_v<_Remove_cvref_t<_Other>, _Ebco_base>, int> = 0>
    explicit _Ebco_base(_Other&& _Val) _NOEXCEPT_COND(is_nothrow_constructible_v<_Ty, _Other>)
        : _Ty(_STD forward<_Other>(_Val)) {}

    _Ty& _Get_val() noexcept {
        return *this;
    }

    const _Ty& _Get_val() const noexcept {
        return *this;
    }
};

template <class _Ty>
class _Ebco_base<_Ty, false> { // Empty Base Class Optimization, inactive
private:
    _Ty _Myval;

protected:
    template <class _Other, enable_if_t<!is_same_v<_Remove_cvref_t<_Other>, _Ebco_base>, int> = 0>
    explicit _Ebco_base(_Other&& _Val) _NOEXCEPT_COND(is_nothrow_constructible_v<_Ty, _Other>)
        : _Myval(_STD forward<_Other>(_Val)) {}

    _Ty& _Get_val() noexcept {
        return _Myval;
    }

    const _Ty& _Get_val() const noexcept {
        return _Myval;
    }
};

#if _HAS_CXX20
// STRUCT identity
struct identity {
    using is_transparent = int;

    template <class _Ty>
    [[nodiscard]] constexpr _Ty&& operator()(_Ty&& _Left) const noexcept {
        return _STD forward<_Ty>(_Left);
    }
};
#endif // _HAS_CXX20

// FUNCTION TEMPLATE not_fn
struct _Not_fn_tag {};

template <class _Decayed>
class _Not_fn : private _Ebco_base<_Decayed> { // wrap a callable object to be negated
private:
    using _Mybase = _Ebco_base<_Decayed>;

public:
    template <class _Callable, class _Tag, enable_if_t<is_same_v<_Tag, _Not_fn_tag>, int> = 0>
    explicit _Not_fn(_Callable&& _Obj, _Tag)
        _NOEXCEPT_COND(is_nothrow_constructible_v<_Decayed, _Callable>) // strengthened
        : _Mybase(_STD forward<_Callable>(_Obj)) { // store a callable object
    }

    _Not_fn(const _Not_fn&) = default;
    _Not_fn(_Not_fn&&)      = default;

    template <class... _Types>
        auto operator()(_Types&&... _Args) &
#ifndef __EDG__ // TRANSITION, VSO#604398
        _NOEXCEPT_COND(noexcept(!_STD invoke(this->_Get_val(),
            _STD forward<_Types>(_Args)...))) // strengthened
#endif // __EDG__
        -> decltype(!_STD declval<invoke_result_t<_Decayed&, _Types...>>()) { // call modifiable lvalue
        return !_STD invoke(this->_Get_val(), _STD forward<_Types>(_Args)...);
    }

    template <class... _Types>
    auto operator()(_Types&&... _Args) const&
#ifndef __EDG__ // TRANSITION, VSO#604398
        _NOEXCEPT_COND(noexcept(!_STD invoke(this->_Get_val(),
            _STD forward<_Types>(_Args)...))) // strengthened
#endif // __EDG__
        -> decltype(!_STD declval<invoke_result_t<const _Decayed&, _Types...>>()) { // call const lvalue
        return !_STD invoke(this->_Get_val(), _STD forward<_Types>(_Args)...);
    }

    template <class... _Types>
        auto operator()(_Types&&... _Args) &&
#ifndef __EDG__ // TRANSITION, VSO#604398
        _NOEXCEPT_COND(noexcept(!_STD invoke(_STD move(this->_Get_val()),
            _STD forward<_Types>(_Args)...))) // strengthened
#endif // __EDG__
        -> decltype(!_STD declval<invoke_result_t<_Decayed, _Types...>>()) { // call modifiable rvalue
        return !_STD invoke(_STD move(this->_Get_val()), _STD forward<_Types>(_Args)...);
    }

    template <class... _Types>
    auto operator()(_Types&&... _Args) const&&
#ifndef __EDG__ // TRANSITION, VSO#604398
        _NOEXCEPT_COND(noexcept(!_STD invoke(_STD move(this->_Get_val()),
            _STD forward<_Types>(_Args)...))) // strengthened
#endif // __EDG__
        -> decltype(!_STD declval<invoke_result_t<const _Decayed, _Types...>>()) { // call const rvalue
        return !_STD invoke(_STD move(this->_Get_val()), _STD forward<_Types>(_Args)...);
    }
};

template <class _Callable>
_NODISCARD _Not_fn<decay_t<_Callable>> not_fn(_Callable&& _Obj)
    _NOEXCEPT_COND(is_nothrow_constructible_v<decay_t<_Callable>, _Callable>) // strengthened
{ // wrap a callable object to be negated
    return _Not_fn<decay_t<_Callable>>(_STD forward<_Callable>(_Obj), _Not_fn_tag{});
}
#endif // _HAS_CXX17

// IMPLEMENT function

// CLASS bad_function_call
class bad_function_call : public exception { // exception thrown when an empty std::function is called
public:
    bad_function_call() noexcept { // construct
    }

    _NODISCARD virtual const char* __CLR_OR_THIS_CALL what() const
        noexcept override { // return pointer to message string
        return "bad function call";
    }
};

[[noreturn]] _CRTIMP2_PURE void __CLRCALL_PURE_OR_CDECL _Xbad_function_call();

// FUNCTION TEMPLATE _Test_callable
template <class _Fty>
class function;

template <class _Ty>
inline bool _Test_callable(
    const _Ty& _Arg, true_type) noexcept { // std::function must store non-null testable callable objects
    return !!_Arg;
}

template <class _Ty>
inline bool _Test_callable(const _Ty&, false_type) noexcept { // std::function must store arbitrary callable objects
    return true;
}

template <class _Ty>
inline bool _Test_callable(const _Ty& _Arg) noexcept { // determine whether std::function must store _Arg
    bool_constant<is_member_pointer_v<_Ty> || (is_pointer_v<_Ty> && is_function_v<remove_pointer_t<_Ty>>)> _Testable;
    return _Test_callable(_Arg, _Testable);
}

template <class _Fty>
inline bool _Test_callable(const function<_Fty>& _Arg) noexcept { // determine whether std::function must store _Arg
    return !!_Arg;
}

#pragma warning(push)
#pragma warning(disable : 4265) // class has virtual functions, but destructor is not virtual
// CLASS TEMPLATE _Func_base
template <class _Rx,
    class... _Types>
class __declspec(novtable) _Func_base { // abstract base for implementation types
public:
    virtual _Func_base* _Copy(void*) const                 = 0;
    virtual _Func_base* _Move(void*)                       = 0;
    virtual _Rx _Do_call(_Types&&...)                      = 0;
    virtual const type_info& _Target_type() const noexcept = 0;
    virtual void _Delete_this(bool) noexcept               = 0;

#if _HAS_STATIC_RTTI
    const void* _Target(const type_info& _Info) const noexcept { // return pointer to stored object of type _Info
        return _Target_type() == _Info ? _Get() : nullptr;
    }
#endif // _HAS_STATIC_RTTI

    _Func_base()                  = default;
    _Func_base(const _Func_base&) = delete;
    _Func_base& operator=(const _Func_base&) = delete;
    // dtor non-virtual due to _Delete_this()

private:
    virtual const void* _Get() const noexcept = 0;
};
#pragma warning(pop)

// ALIAS TEMPLATE _Is_large
constexpr size_t _Space_size = (_Small_object_num_ptrs - 1) * sizeof(void*);

template <class _Impl> // determine whether _Impl must be dynamically allocated
using _Is_large = bool_constant<(_Space_size < sizeof(_Impl)) || !_Impl::_Nothrow_move::value>;

#pragma warning(push)
#pragma warning(disable : 4265) // class has virtual functions, but destructor is not virtual

#if _HAS_FUNCTION_ALLOCATOR_SUPPORT
// CLASS TEMPLATE _Func_impl
template <class _Callable, class _Alloc, class _Rx, class... _Types>
class _Func_impl final
    : public _Func_base<_Rx, _Types...> { // derived class for specific implementation types that use allocators
public:
    using _Mybase        = _Func_base<_Rx, _Types...>;
    using _Myalty        = _Rebind_alloc_t<_Alloc, _Func_impl>;
    using _Myalty_traits = allocator_traits<_Myalty>;
    using _Nothrow_move  = is_nothrow_move_constructible<_Callable>;

    template <class _Other1, class _Other2>
    _Func_impl(_Other1&& _Val, _Other2&& _Ax)
        : _Mypair(_One_then_variadic_args_t(), _STD forward<_Other2>(_Ax), _STD forward<_Other1>(_Val)) { // construct
    }

    // dtor non-virtual due to _Delete_this()

private:
    virtual _Mybase* _Copy(void* _Where) const override { // return clone of *this
        return _Clone(_Where, _Is_large<_Func_impl>{});
    }

    _Mybase* _Clone(void*, true_type) const { // return clone of *this, large (dynamically allocated)
        return _Alloc_rebound<_Func_impl>(_Myax(), _Callee(), _Myax());
    }

    _Mybase* _Clone(void* _Where, false_type) const { // return clone of *this, small (locally stored)
        _Myalty _Al(_Myax());
        _Func_impl* _Ptr = static_cast<_Func_impl*>(_Where);
        _Myalty_traits::construct(_Al, _Ptr, _Callee(), _Myax());
        return _Ptr;
    }

    virtual _Mybase* _Move(void* _Where) override { // return clone of *this
        _Myalty _Al(_Myax());
        _Func_impl* _Ptr = static_cast<_Func_impl*>(_Where);
        _Myalty_traits::construct(_Al, _Ptr, _STD move(_Callee()), _STD move(_Myax()));
        return _Ptr;
    }

    virtual _Rx _Do_call(_Types&&... _Args) override { // call wrapped function
        auto& _The_callee = _Callee();
        return _Invoker_ret<_Rx>::_Call(_The_callee, _STD forward<_Types>(_Args)...);
    }

    virtual const type_info& _Target_type() const noexcept override { // return type information for stored object
#if _HAS_STATIC_RTTI
        return typeid(_Callable);
#else // _HAS_STATIC_RTTI
        return typeid(void);
#endif // _HAS_STATIC_RTTI
    }

    virtual const void* _Get() const noexcept override { // return address of stored object
        return _STD addressof(_Callee());
    }

    virtual void _Delete_this(bool _Deallocate) noexcept override { // destroy self
        _Myalty _Al(_Myax());
        _Myalty_traits::destroy(_Al, this);
        if (_Deallocate) {
            _Deallocate_plain(_Al, this);
        }
    }

    _Compressed_pair<_Alloc, _Callable> _Mypair;

    _Alloc& _Myax() noexcept { // return reference to allocator
        return _Mypair._Get_first();
    }

    const _Alloc& _Myax() const noexcept { // return const reference to allocator
        return _Mypair._Get_first();
    }

    _Callable& _Callee() noexcept { // return reference to wrapped function
        return _Mypair._Myval2;
    }

    const _Callable& _Callee() const noexcept { // return const reference to wrapped function
        return _Mypair._Myval2;
    }
};
#endif // _HAS_FUNCTION_ALLOCATOR_SUPPORT

// CLASS TEMPLATE _Func_impl_no_alloc
template <class _Callable, class _Rx, class... _Types>
class _Func_impl_no_alloc final
    : public _Func_base<_Rx, _Types...> { // derived class for specific implementation types that don't use allocators
public:
    using _Mybase       = _Func_base<_Rx, _Types...>;
    using _Nothrow_move = is_nothrow_move_constructible<_Callable>;

    template <class _Other, class = enable_if_t<!is_same_v<_Func_impl_no_alloc, decay_t<_Other>>>>
    explicit _Func_impl_no_alloc(_Other&& _Val) : _Callee(_STD forward<_Other>(_Val)) { // construct
    }

    // dtor non-virtual due to _Delete_this()

private:
    virtual _Mybase* _Copy(void* _Where) const override { // return clone of *this
        return _Clone(_Where, _Is_large<_Func_impl_no_alloc>{});
    }

    _Mybase* _Clone(void*, true_type) const { // return clone of *this, large (dynamically allocated)
        return _Global_new<_Func_impl_no_alloc>(_Callee);
    }

    _Mybase* _Clone(void* _Where, false_type) const { // return clone of *this, small (locally stored)
        return ::new (_Where) _Func_impl_no_alloc(_Callee);
    }

    virtual _Mybase* _Move(void* _Where) override { // return clone of *this
        return ::new (_Where) _Func_impl_no_alloc(_STD move(_Callee));
    }

    virtual _Rx _Do_call(_Types&&... _Args) override { // call wrapped function
        return _Invoker_ret<_Rx>::_Call(_Callee, _STD forward<_Types>(_Args)...);
    }

    virtual const type_info& _Target_type() const noexcept override { // return type information for stored object
#if _HAS_STATIC_RTTI
        return typeid(_Callable);
#else // _HAS_STATIC_RTTI
        return typeid(void);
#endif // _HAS_STATIC_RTTI
    }

    virtual const void* _Get() const noexcept override { // return address of stored object
        return _STD addressof(_Callee);
    }

    virtual void _Delete_this(bool _Dealloc) noexcept override { // destroy self
        this->~_Func_impl_no_alloc();
        if (_Dealloc) {
            _Deallocate<alignof(_Func_impl_no_alloc)>(this, sizeof(_Func_impl_no_alloc));
        }
    }

    _Callable _Callee;
};
#pragma warning(pop)

// CLASS TEMPLATE _Func_class
template <class _Ret,
    class... _Types>
class _Func_class : public _Arg_types<_Types...> { // implement function template
public:
    using result_type = _Ret;

    using _Ptrt = _Func_base<_Ret, _Types...>;

    _Func_class() noexcept { // construct without stored object
        _Set(nullptr);
    }

    _Ret operator()(_Types... _Args) const { // call through stored object
        if (_Empty()) {
            _Xbad_function_call();
        }
        const auto _Impl = _Getimpl();
        return _Impl->_Do_call(_STD forward<_Types>(_Args)...);
    }

    ~_Func_class() noexcept { // destroy the object
        _Tidy();
    }

protected:
    template <class _Fx, class _Function>
    using _Enable_if_callable_t =
        enable_if_t<conjunction_v<negation<is_same<decay_t<_Fx>, _Function>>, _Is_invocable_r<_Ret, _Fx, _Types...>>>;

    bool _Empty() const noexcept { // return true if no stored object
        return _Getimpl() == nullptr;
    }

    void _Reset_copy(const _Func_class& _Right) { // copy _Right's stored object
        if (!_Right._Empty()) {
            _Set(_Right._Getimpl()->_Copy(_Getspace()));
        }
    }

    void _Reset_move(_Func_class&& _Right) { // move _Right's stored object
        if (!_Right._Empty()) {
            if (_Right._Local()) { // move and tidy
                _Set(_Right._Getimpl()->_Move(_Getspace()));
                _Right._Tidy();
            } else { // steal from _Right
                _Set(_Right._Getimpl());
                _Right._Set(nullptr);
            }
        }
    }

    template <class _Fx>
    void _Reset(_Fx&& _Val) { // store copy of _Val
        if (!_Test_callable(_Val)) { // null member pointer/function pointer/std::function
            return; // already empty
        }

        using _Impl = _Func_impl_no_alloc<decay_t<_Fx>, _Ret, _Types...>;
        _Reset_impl<_Impl>(_STD forward<_Fx>(_Val), _Is_large<_Impl>{});
    }

    template <class _Myimpl, class _Fx>
    void _Reset_impl(_Fx&& _Val, true_type) { // store copy of _Val, large (dynamically allocated)
        _Set(_Global_new<_Myimpl>(_STD forward<_Fx>(_Val)));
    }

    template <class _Myimpl, class _Fx>
    void _Reset_impl(_Fx&& _Val, false_type) { // store copy of _Val, small (locally stored)
        _Set(::new (_Getspace()) _Myimpl(_STD forward<_Fx>(_Val)));
    }

#if _HAS_FUNCTION_ALLOCATOR_SUPPORT
    template <class _Fx, class _Alloc>
    void _Reset_alloc(_Fx&& _Val, const _Alloc& _Ax) { // store copy of _Val with allocator
        if (!_Test_callable(_Val)) { // null member pointer/function pointer/std::function
            return; // already empty
        }

        using _Myimpl = _Func_impl<decay_t<_Fx>, _Alloc, _Ret, _Types...>;
        _Myimpl* _Ptr = nullptr;

        _Rebind_alloc_t<_Alloc, _Myimpl> _Al(_Ax);
        _Reset_impl_alloc(_STD forward<_Fx>(_Val), _Ax, _Ptr, _Al, _Is_large<_Myimpl>{});
    }

    template <class _Fx, class _Alloc, class _Myimpl, class _Alimpl>
    void _Reset_impl_alloc(_Fx&& _Val, const _Alloc& _Ax, _Myimpl*, _Alimpl& _Al,
        true_type) { // store copy of _Val with allocator, large (dynamically allocated)
        _Set(_Unfancy(_Alloc_new(_Al, _STD forward<_Fx>(_Val), _Ax)));
    }

    template <class _Fx, class _Alloc, class _Myimpl, class _Alimpl>
    void _Reset_impl_alloc(_Fx&& _Val, const _Alloc& _Ax, _Myimpl*, _Alimpl& _Al,
        false_type) { // store copy of _Val with allocator, small (locally stored)
        _Myimpl* _Ptr = static_cast<_Myimpl*>(_Getspace());
        allocator_traits<_Alimpl>::construct(_Al, _Ptr, _STD forward<_Fx>(_Val), _Ax);
        _Set(_Ptr);
    }
#endif // _HAS_FUNCTION_ALLOCATOR_SUPPORT

    void _Tidy() noexcept { // clean up
        if (!_Empty()) { // destroy callable object and maybe delete it
            _Getimpl()->_Delete_this(!_Local());
            _Set(nullptr);
        }
    }

    void _Swap(_Func_class& _Right) noexcept { // swap contents with contents of _Right
        if (!_Local() && !_Right._Local()) { // just swap pointers
            _Ptrt* _Temp = _Getimpl();
            _Set(_Right._Getimpl());
            _Right._Set(_Temp);
        } else { // do three-way move
            _Func_class _Temp;
            _Temp._Reset_move(_STD move(*this));
            _Reset_move(_STD move(_Right));
            _Right._Reset_move(_STD move(_Temp));
        }
    }

#if _HAS_STATIC_RTTI
    const type_info& _Target_type() const noexcept { // return type information for stored object
        return _Getimpl() ? _Getimpl()->_Target_type() : typeid(void);
    }

    const void* _Target(const type_info& _Info) const noexcept { // return pointer to stored object
        return _Getimpl() ? _Getimpl()->_Target(_Info) : nullptr;
    }
#endif // _HAS_STATIC_RTTI

private:
    bool _Local() const noexcept { // test for locally stored copy of object
        return _Getimpl() == _Getspace();
    }

    union _Storage { // storage for small objects (basic_string is small)
        max_align_t _Dummy1; // for maximum alignment
        char _Dummy2[_Space_size]; // to permit aliasing
        _Ptrt* _Ptrs[_Small_object_num_ptrs]; // _Ptrs[_Small_object_num_ptrs - 1] is reserved
    };

    _Storage _Mystorage;
    enum { _EEN_IMPL = _Small_object_num_ptrs - 1 }; // helper for expression evaluator
    _Ptrt* _Getimpl() const noexcept { // get pointer to object
        return _Mystorage._Ptrs[_Small_object_num_ptrs - 1];
    }

    void _Set(_Ptrt* _Ptr) noexcept { // store pointer to object
        _Mystorage._Ptrs[_Small_object_num_ptrs - 1] = _Ptr;
    }

    void* _Getspace() noexcept { // get pointer to storage space
        return &_Mystorage;
    }

    const void* _Getspace() const noexcept { // get pointer to storage space
        return &_Mystorage;
    }
};

// STRUCT TEMPLATE _Get_function_impl
template <class _Tx>
struct _Get_function_impl;

#define _GET_FUNCTION_IMPL(CALL_OPT, X1, X2, X3)                                                  \
    template <class _Ret, class... _Types>                                                        \
    struct _Get_function_impl<_Ret CALL_OPT(_Types...)> { /* determine type from argument list */ \
        using type = _Func_class<_Ret, _Types...>;                                                \
    };

_NON_MEMBER_CALL(_GET_FUNCTION_IMPL, X1, X2, X3)
#undef _GET_FUNCTION_IMPL

// CLASS TEMPLATE function
template <class _Fty>
class function : public _Get_function_impl<_Fty>::type { // wrapper for callable objects
private:
    using _Mybase = typename _Get_function_impl<_Fty>::type;

public:
    function() noexcept { // construct empty function wrapper
    }

    function(nullptr_t) noexcept { // construct empty function wrapper from null pointer
    }

    function(const function& _Right) { // construct holding copy of _Right
        this->_Reset_copy(_Right);
    }

    template <class _Fx, class = typename _Mybase::template _Enable_if_callable_t<_Fx&, function>>
    function(_Fx _Func) { // construct wrapper holding copy of _Func
        this->_Reset(_STD move(_Func));
    }

#if _HAS_FUNCTION_ALLOCATOR_SUPPORT
    template <class _Alloc>
    function(allocator_arg_t, const _Alloc&) noexcept { // construct empty function wrapper, allocator
    }

    template <class _Alloc>
    function(allocator_arg_t, const _Alloc&,
        nullptr_t) noexcept { // construct empty function wrapper from null pointer, allocator
    }

    template <class _Alloc>
    function(allocator_arg_t, const _Alloc& _Ax,
        const function& _Right) { // construct wrapper holding copy of _Right, allocator
        this->_Reset_alloc(_Right, _Ax);
    }

    template <class _Fx, class _Alloc, class = typename _Mybase::template _Enable_if_callable_t<_Fx&, function>>
    function(allocator_arg_t, const _Alloc& _Ax, _Fx _Func) { // construct wrapper holding copy of _Func, allocator
        this->_Reset_alloc(_STD move(_Func), _Ax);
    }
#endif // _HAS_FUNCTION_ALLOCATOR_SUPPORT

    function& operator=(const function& _Right) { // assign _Right
        function(_Right).swap(*this);
        return *this;
    }

    function(function&& _Right) { // construct holding moved copy of _Right
        this->_Reset_move(_STD move(_Right));
    }

#if _HAS_FUNCTION_ALLOCATOR_SUPPORT
    template <class _Alloc>
    function(allocator_arg_t, const _Alloc& _Al,
        function&& _Right) { // construct wrapper holding moved copy of _Right, allocator
        this->_Reset_alloc(_STD move(_Right), _Al);
    }
#endif // _HAS_FUNCTION_ALLOCATOR_SUPPORT

    function& operator=(function&& _Right) { // assign by moving _Right
        if (this != _STD addressof(_Right)) { // clean up and copy
            this->_Tidy();
            this->_Reset_move(_STD move(_Right));
        }
        return *this;
    }

    template <class _Fx, class = typename _Mybase::template _Enable_if_callable_t<decay_t<_Fx>&, function>>
    function& operator=(_Fx&& _Func) { // assign function object _Func
        function(_STD forward<_Fx>(_Func)).swap(*this);
        return *this;
    }

#if _HAS_FUNCTION_ALLOCATOR_SUPPORT
    template <class _Fx, class _Alloc>
    void assign(_Fx&& _Func, const _Alloc& _Ax) { // assign wrapper holding copy of _Func, allocator
        function(allocator_arg, _Ax, _STD forward<_Fx>(_Func)).swap(*this);
    }
#endif // _HAS_FUNCTION_ALLOCATOR_SUPPORT

    function& operator=(nullptr_t) noexcept { // clear function object
        this->_Tidy();
        return *this;
    }

    template <class _Fx>
    function& operator=(
        reference_wrapper<_Fx> _Func) noexcept { // assign wrapper holding reference_wrapper to function object
        this->_Tidy();
        this->_Reset(_Func);
        return *this;
    }

    void swap(function& _Right) noexcept { // swap with _Right
        this->_Swap(_Right);
    }

    explicit operator bool() const noexcept { // test if wrapper holds function object
        return !this->_Empty();
    }

#if _HAS_STATIC_RTTI
    _NODISCARD const type_info& target_type() const noexcept { // return type_info object for target type
        return this->_Target_type();
    }

    template <class _Fx>
    _NODISCARD _Fx* target() noexcept { // return pointer to target object
        return reinterpret_cast<_Fx*>(const_cast<void*>(this->_Target(typeid(_Fx))));
    }

    template <class _Fx>
    _NODISCARD const _Fx* target() const noexcept { // return pointer to target object
        return reinterpret_cast<const _Fx*>(this->_Target(typeid(_Fx)));
    }
#else // _HAS_STATIC_RTTI
    const type_info& target_type() const noexcept = delete; // requires static RTTI

    template <class _Fx>
    _Fx* target() noexcept = delete; // requires static RTTI

    template <class _Fx>
    const _Fx* target() const noexcept = delete; // requires static RTTI
#endif // _HAS_STATIC_RTTI
};

#if _HAS_CXX17

#define _FUNCTION_POINTER_DEDUCTION_GUIDE(CALL_OPT, X1, X2, X3) \
    template <class _Ret, class... _Types>                      \
    function(_Ret(CALL_OPT*)(_Types...))->function<_Ret(_Types...)>; // intentionally discards CALL_OPT

_NON_MEMBER_CALL(_FUNCTION_POINTER_DEDUCTION_GUIDE, X1, X2, X3)
#undef _FUNCTION_POINTER_DEDUCTION_GUIDE

// STRUCT TEMPLATE _Deduce_signature
template <class _Fx,
    class = void>
struct _Deduce_signature { // can't deduce signature when &_Fx::operator() is missing, inaccessible, or ambiguous
};

template <class _Fx>
struct _Deduce_signature<_Fx, void_t<decltype(&_Fx::operator())>>
    : _Is_memfunptr<decltype(&_Fx::operator())>::_Guide_type { // N4687 23.14.13.2.1 [func.wrap.func.con]/12
};

template <class _Fx>
function(_Fx)->function<typename _Deduce_signature<_Fx>::type>;
#endif // _HAS_CXX17

// FUNCTION TEMPLATE swap
template <class _Fty>
inline void swap(
    function<_Fty>& _Left, function<_Fty>& _Right) noexcept { // swap contents of _Left with contents of _Right
    _Left.swap(_Right);
}

// TEMPLATE NULL POINTER COMPARISONS
template <class _Fty>
_NODISCARD inline bool operator==(const function<_Fty>& _Other, nullptr_t) noexcept { // compare to null pointer
    return !_Other;
}

template <class _Fty>
_NODISCARD inline bool operator==(nullptr_t, const function<_Fty>& _Other) noexcept { // compare to null pointer
    return !_Other;
}

template <class _Fty>
_NODISCARD inline bool operator!=(const function<_Fty>& _Other, nullptr_t) noexcept { // compare to null pointer
    return static_cast<bool>(_Other);
}

template <class _Fty>
_NODISCARD inline bool operator!=(nullptr_t, const function<_Fty>& _Other) noexcept { // compare to null pointer
    return static_cast<bool>(_Other);
}

// PLACEHOLDERS
template <int _Nx>
struct _Ph { // placeholder
};

template <class _Tx>
struct is_placeholder : integral_constant<int, 0> { // template to indicate that _Tx is not a placeholder
};

template <int _Nx>
struct is_placeholder<_Ph<_Nx>>
    : integral_constant<int, _Nx> { // template specialization to indicate that _Ph<_Nx> is a placeholder
};

template <class _Tx>
struct is_placeholder<const _Tx> : is_placeholder<_Tx>::type { // ignore cv-qualifiers
};

template <class _Tx>
struct is_placeholder<volatile _Tx> : is_placeholder<_Tx>::type { // ignore cv-qualifiers
};

template <class _Tx>
struct is_placeholder<const volatile _Tx> : is_placeholder<_Tx>::type { // ignore cv-qualifiers
};

template <class _Ty>
_INLINE_VAR constexpr int is_placeholder_v = is_placeholder<_Ty>::value;

// CLASS TEMPLATE _Binder FORWARD DECLARATION
template <class _Ret, class _Fx, class... _Types>
class _Binder;

// STRUCT TEMPLATE is_bind_expression
template <class _Tx>
struct is_bind_expression : false_type { // template to indicate that _Tx is not a bind expression
};

template <class _Ret, class _Fx, class... _Types>
struct is_bind_expression<_Binder<_Ret, _Fx, _Types...>>
    : true_type { // template specialization to indicate a bind expression
};

template <class _Tx>
struct is_bind_expression<const _Tx> : is_bind_expression<_Tx>::type { // ignore cv-qualifiers
};

template <class _Tx>
struct is_bind_expression<volatile _Tx> : is_bind_expression<_Tx>::type { // ignore cv-qualifiers
};

template <class _Tx>
struct is_bind_expression<const volatile _Tx> : is_bind_expression<_Tx>::type { // ignore cv-qualifiers
};

template <class _Ty>
_INLINE_VAR constexpr bool is_bind_expression_v = is_bind_expression<_Ty>::value;

// FUNCTION TEMPLATE _Fix_arg
template <class _Cv_TiD, bool = _Is_specialization_v<remove_cv_t<_Cv_TiD>, reference_wrapper>,
    bool = is_bind_expression_v<_Cv_TiD>, int = is_placeholder_v<_Cv_TiD>>
struct _Select_fixer;

template <class _Cv_TiD>
struct _Select_fixer<_Cv_TiD, true, false, 0> { // reference_wrapper fixer
    template <class _Untuple>
    static auto _Fix(_Cv_TiD& _Tid, _Untuple &&) -> typename _Cv_TiD::type& { // unwrap a reference_wrapper
        return _Tid.get();
    }
};

template <class _Cv_TiD>
struct _Select_fixer<_Cv_TiD, false, true, 0> { // nested bind fixer
#pragma warning(push)
#pragma warning(disable : 4100) // TRANSITION, VSO#181496, unreferenced formal parameter
    template <class _Untuple, size_t... _Jx>
    static auto _Apply(_Cv_TiD& _Tid, _Untuple&& _Ut,
        index_sequence<_Jx...>) -> decltype(_Tid(_STD get<_Jx>(_STD move(_Ut))...)) { // call a nested bind expression
        return _Tid(_STD get<_Jx>(_STD move(_Ut))...);
    }
#pragma warning(pop)

    template <class _Untuple>
    static auto _Fix(_Cv_TiD& _Tid, _Untuple&& _Ut) -> decltype(_Apply(_Tid, _STD move(_Ut),
        make_index_sequence<tuple_size_v<_Untuple>>())) { // call a nested bind expression
        return _Apply(_Tid, _STD move(_Ut), make_index_sequence<tuple_size_v<_Untuple>>());
    }
};

template <class _Cv_TiD>
struct _Select_fixer<_Cv_TiD, false, false, 0> { // identity fixer
    template <class _Untuple>
    static _Cv_TiD& _Fix(_Cv_TiD& _Tid, _Untuple&&) { // pass a bound argument as an lvalue (important!)
        return _Tid;
    }
};

template <class _Cv_TiD, int _Jx>
struct _Select_fixer<_Cv_TiD, false, false, _Jx> { // placeholder fixer
    static_assert(_Jx > 0, "invalid is_placeholder value");

    template <class _Untuple>
    static auto _Fix(_Cv_TiD&, _Untuple&& _Ut)
        -> decltype(_STD get<_Jx - 1>(_STD move(_Ut))) { // choose the Jth unbound argument (1-based indexing)
        return _STD get<_Jx - 1>(_STD move(_Ut));
    }
};

template <class _Cv_TiD, class _Untuple>
inline auto _Fix_arg(_Cv_TiD& _Tid, _Untuple&& _Ut)
    -> decltype(_Select_fixer<_Cv_TiD>::_Fix(_Tid, _STD move(_Ut))) { // translate an argument for bind
    return _Select_fixer<_Cv_TiD>::_Fix(_Tid, _STD move(_Ut));
}

#pragma warning(push)
#pragma warning(disable : 4100) // TRANSITION, VSO#181496, unreferenced formal parameter
// FUNCTION TEMPLATE _Call_binder
template <class _Ret, size_t... _Ix, class _Cv_FD, class _Cv_tuple_TiD, class _Untuple>
inline auto _Call_binder(_Invoker_ret<_Ret>, index_sequence<_Ix...>, _Cv_FD& _Obj, _Cv_tuple_TiD& _Tpl, _Untuple&& _Ut)
    -> decltype(_Invoker_ret<_Ret>::_Call(
        _Obj, _Fix_arg(_STD get<_Ix>(_Tpl), _STD move(_Ut))...)) { // bind() and bind<R>() invocation
    return _Invoker_ret<_Ret>::_Call(_Obj, _Fix_arg(_STD get<_Ix>(_Tpl), _STD move(_Ut))...);
}
#pragma warning(pop)

// CLASS TEMPLATE _Binder
template <class _Ret>
struct _Forced_result_type { // used by bind<R>()
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ret result_type;
};

template <class _Ret,
    class _Fx>
struct _Binder_result_type { // provide result_type (sometimes)
    using _Decayed = decay_t<_Fx>;

    using _All_weak_types = typename _Weak_types<_Decayed>::type;

    using type =
        conditional_t<is_same_v<_Ret, _Unforced>, _Weak_result_type<_All_weak_types>, _Forced_result_type<_Ret>>;
};

template <class _Ret, class _Fx, class... _Types>
class _Binder : public _Binder_result_type<_Ret, _Fx>::type { // wrap bound callable object and arguments
private:
    using _Seq    = index_sequence_for<_Types...>;
    using _First  = decay_t<_Fx>;
    using _Second = tuple<decay_t<_Types>...>;

    _Compressed_pair<_First, _Second> _Mypair;

public:
    explicit _Binder(_Fx&& _Func, _Types&&... _Args)
        : _Mypair(_One_then_variadic_args_t(), _STD forward<_Fx>(_Func),
              _STD forward<_Types>(_Args)...) { // construct from forwarded callable object and arguments
    }

#define _BINDER_OPERATOR(CONST_OPT)                                                                           \
    template <class... _Unbound>                                                                              \
    auto operator()(_Unbound&&... _Unbargs)                                                                   \
        CONST_OPT->decltype(_Call_binder(_Invoker_ret<_Ret>(), _Seq(), _Mypair._Get_first(), _Mypair._Myval2, \
            _STD forward_as_tuple(_STD forward<_Unbound>(                                                     \
                _Unbargs)...))) { /* invoke bound callable object with bound/unbound arguments */             \
        return _Call_binder(_Invoker_ret<_Ret>(), _Seq(), _Mypair._Get_first(), _Mypair._Myval2,              \
            _STD forward_as_tuple(_STD forward<_Unbound>(_Unbargs)...));                                      \
    }

    _CLASS_DEFINE_CONST(_BINDER_OPERATOR)
#undef _BINDER_OPERATOR
};

// FUNCTION TEMPLATE bind (implicit return type)
template <class _Fx, class... _Types>
_NODISCARD inline _Binder<_Unforced, _Fx, _Types...> bind(
    _Fx&& _Func, _Types&&... _Args) { // bind a callable object with an implicit return type
    return _Binder<_Unforced, _Fx, _Types...>(_STD forward<_Fx>(_Func), _STD forward<_Types>(_Args)...);
}

// FUNCTION TEMPLATE bind (explicit return type)
template <class _Ret, class _Fx, class... _Types>
_NODISCARD _Binder<_Ret, _Fx, _Types...> bind(
    _Fx&& _Func, _Types&&... _Args) { // bind a callable object with an explicit return type
    return _Binder<_Ret, _Fx, _Types...>(_STD forward<_Fx>(_Func), _STD forward<_Types>(_Args)...);
}

// PLACEHOLDER ARGUMENTS
namespace placeholders { // placeholders
    _INLINE_VAR constexpr _Ph<1> _1{};
    _INLINE_VAR constexpr _Ph<2> _2{};
    _INLINE_VAR constexpr _Ph<3> _3{};
    _INLINE_VAR constexpr _Ph<4> _4{};
    _INLINE_VAR constexpr _Ph<5> _5{};
    _INLINE_VAR constexpr _Ph<6> _6{};
    _INLINE_VAR constexpr _Ph<7> _7{};
    _INLINE_VAR constexpr _Ph<8> _8{};
    _INLINE_VAR constexpr _Ph<9> _9{};
    _INLINE_VAR constexpr _Ph<10> _10{};
    _INLINE_VAR constexpr _Ph<11> _11{};
    _INLINE_VAR constexpr _Ph<12> _12{};
    _INLINE_VAR constexpr _Ph<13> _13{};
    _INLINE_VAR constexpr _Ph<14> _14{};
    _INLINE_VAR constexpr _Ph<15> _15{};
    _INLINE_VAR constexpr _Ph<16> _16{};
    _INLINE_VAR constexpr _Ph<17> _17{};
    _INLINE_VAR constexpr _Ph<18> _18{};
    _INLINE_VAR constexpr _Ph<19> _19{};
    _INLINE_VAR constexpr _Ph<20> _20{};
} // namespace placeholders

#if _HAS_FUNCTION_ALLOCATOR_SUPPORT
// STRUCT TEMPLATE uses_allocator
template <class _Fty, class _Alloc>
struct uses_allocator<function<_Fty>, _Alloc> : true_type { // true_type if container allocator enabled
};
#endif // _HAS_FUNCTION_ALLOCATOR_SUPPORT

#if _HAS_CXX17
// HETEROGENEOUS MEMORY BLOCK UTILITIES
inline void _Add_alloc_size(size_t& _Size, const size_t _Size_added,
    const size_t _Alignment) { // moves _Size up to account for storing an object of size _Size_added with alignment
                               // _Alignment in a memory buffer
                               // assumes that the memory buffer will be allocated for the "worst" alignment used in the
                               // resulting buffer
    const size_t _Align_masked = _Size & (_Alignment - 1u);
    _Size += _Size_added;
    if (_Align_masked != 0) {
        _Size += _Alignment - _Align_masked;
    }
}

template <class _Ty>
inline void _Add_alloc_size(size_t& _Size) { // moves _Size up to account for allocating a _Ty
    _Add_alloc_size(_Size, sizeof(_Ty), alignof(_Ty));
}

template <class _Ty>
inline void _Add_alloc_size(
    size_t& _Size, const size_t _Count) { // moves _Size up to account for allocating an array of _Count _Ty instances
    if (static_cast<size_t>(-1) / sizeof(_Ty) < _Count) {
        _Xbad_alloc();
    }

    _Add_alloc_size(_Size, sizeof(_Ty) * _Count, alignof(_Ty));
}

inline void* _Decode_aligned_block(void*& _Base, size_t _Size,
    const size_t _Alignment) { // "allocates" an object of size _Size and alignment _Alignment from _Base, and shifts
                               // _Base up by the size necessary to decode that object.
    auto _Space  = static_cast<size_t>(-1);
    auto _Result = _STD align(_Alignment, _Size, _Base, _Space);
    _Base        = static_cast<char*>(_Base) + _Size;
    return _Result;
}

template <class _Ty>
inline _Ty* _Decode_aligned_block(void*& _Base) { // "allocates" a _Ty from _Base
    return static_cast<_Ty*>(_Decode_aligned_block(_Base, sizeof(_Ty), alignof(_Ty)));
}

template <class _Ty>
inline _Ty* _Decode_aligned_block(
    void*& _Base, const size_t _Count) { // "allocates" an array of _Count _Ty instances from _Base
    return static_cast<_Ty*>(_Decode_aligned_block(_Base, sizeof(_Ty) * _Count, alignof(_Ty)));
}

// STRUCT _Global_delete
struct _Global_delete {
    void operator()(void* const _Ptr) const {
        ::operator delete(_Ptr);
    }
};

// CLASS TEMPLATE default_searcher
template <class _FwdItHaystack, class _FwdItPat, class _Pred_eq>
inline pair<_FwdItHaystack, _FwdItHaystack> _Search_pair_unchecked(_FwdItHaystack _First1, _FwdItHaystack _Last1,
    _FwdItPat _First2, _FwdItPat _Last2, _Pred_eq& _Eq, forward_iterator_tag,
    forward_iterator_tag) { // find first [_First2, _Last2) satisfying _Eq, arbitrary iterators
    for (;; ++_First1) { // loop until match or end of a sequence
        _FwdItHaystack _Mid1 = _First1;
        for (_FwdItPat _Mid2 = _First2;; ++_Mid1, (void) ++_Mid2) {
            if (_Mid2 == _Last2) {
                return {_First1, _Mid1};
            }

            if (_Mid1 == _Last1) {
                return {_Last1, _Last1};
            }

            if (!_Eq(*_Mid1, *_Mid2)) {
                break;
            }
        }
    }
}

template <class _FwdItHaystack, class _FwdItPat, class _Pred_eq>
inline pair<_FwdItHaystack, _FwdItHaystack> _Search_pair_unchecked(_FwdItHaystack _First1, _FwdItHaystack _Last1,
    _FwdItPat _First2, _FwdItPat _Last2, _Pred_eq& _Eq, random_access_iterator_tag,
    random_access_iterator_tag) { // find first [_First2, _Last2) satisfying _Eq, random-access iterators
    _Iter_diff_t<_FwdItHaystack> _Count1 = _Last1 - _First1;
    _Iter_diff_t<_FwdItPat> _Count2      = _Last2 - _First2;

    for (; _Count2 <= _Count1; ++_First1, (void) --_Count1) { // room for match, try it
        _FwdItHaystack _Mid1 = _First1;
        for (_FwdItPat _Mid2 = _First2;; ++_Mid1, (void) ++_Mid2) {
            if (_Mid2 == _Last2) {
                return {_First1, _Mid1};
            }

            if (!_Eq(*_Mid1, *_Mid2)) {
                break;
            }
        }
    }

    return {_Last1, _Last1};
}

template <class _FwdItPat,
    class _Pred_eq = equal_to<>>
class default_searcher { // functor to search haystacks for needles
public:
    default_searcher(_FwdItPat _First, _FwdItPat _Last, _Pred_eq _Eq = _Pred_eq())
        : _Data{_One_then_variadic_args_t{}, _STD move(_Eq),
              pair<_FwdItPat, _FwdItPat>{_First, _Last}} { // construct a default_searcher
        const auto& _Pat = _Data._Myval2;
        _Adl_verify_range(_Pat.first, _Pat.second);
    }

    template <class _FwdItHaystack>
    _NODISCARD pair<_FwdItHaystack, _FwdItHaystack> operator()(
        _FwdItHaystack _First, _FwdItHaystack _Last) const { // search [_First, _Last) for the searcher's pattern
        _Adl_verify_range(_First, _Last);
        const auto& _Eq  = _Data._Get_first();
        const auto& _Pat = _Data._Myval2;
        _Adl_verify_range(_Pat.first, _Pat.second); // check again to ensure container is not destroyed
        const auto _Result =
            _Search_pair_unchecked(_Get_unwrapped(_First), _Get_unwrapped(_Last), _Get_unwrapped(_Pat.first),
                _Get_unwrapped(_Pat.second), _Eq, _Iter_cat_t<_FwdItHaystack>{}, _Iter_cat_t<_FwdItPat>{});
        _Seek_wrapped(_Last, _Result.second);
        _Seek_wrapped(_First, _Result.first);
        return {_First, _Last};
    }

private:
    _Compressed_pair<_Pred_eq, pair<_FwdItPat, _FwdItPat>> _Data;
};


// STRUCT TEMPLATE _Boyer_moore_hash_delta_1_table
template <class _RanItPat, class _Hash_ty,
    class _Pred_eq>
struct _Boyer_moore_hash_delta_1_table { // stores the Boyer-Moore delta_1 table using a hash table
    using _Value_t = _Iter_value_t<_RanItPat>;
    using _Diff    = _Iter_diff_t<_RanItPat>;

    _Boyer_moore_hash_delta_1_table(_RanItPat _Pat_first_arg, _Unwrapped_t<_RanItPat> _UPat_first,
        const _Diff _Pat_size_arg, _Hash_ty&& _Hash_fn, _Pred_eq&& _Eq)
        : _Pat_first(_Pat_first_arg), _Pat_size(_Pat_size_arg),
          _Map(0, _STD move(_Hash_fn), _STD move(_Eq)) { // initialize a delta_1 hash table
        for (_Diff _Idx = 1; _Idx <= _Pat_size; ++_Idx, (void) ++_UPat_first) {
            _Map.insert_or_assign(*_UPat_first, _Pat_size - _Idx);
        }
    }

    _Diff _Lookup(const _Value_t& _Value)
        const { // lookup the "character" _Value in the table, returning the maximum shift if found
        const auto _Iter = _Map.find(_Value);
        if (_Iter == _Map.end()) {
            return _Pat_size;
        }

        return _Iter->second;
    }

    _Pred_eq _Get_eq() const { // return the comparison predicate
        return _Map.key_eq();
    }

    const _RanItPat _Pat_first;
    const _Diff _Pat_size;

private:
    unordered_map<_Value_t, _Diff, _Hash_ty, _Pred_eq> _Map;
};


// STRUCT TEMPLATE _Boyer_moore_flat_delta_1_table
template <class _RanItPat,
    _Iter_diff_t<_RanItPat> _Limit>
struct _Boyer_moore_flat_delta_1_table { // stores the Boyer-Moore delta_1 table using a plain array lookup
    using _Value_t = _Iter_value_t<_RanItPat>;
    using _Diff    = _Iter_diff_t<_RanItPat>;

    _Boyer_moore_flat_delta_1_table(_RanItPat _Pat_first_arg, _Unwrapped_t<_RanItPat> _UPat_first,
        const _Diff _Pat_size_arg, _Unused_parameter, _Unused_parameter)
        : _Pat_first(_Pat_first_arg), _Pat_size(_Pat_size_arg) { // initialize a delta_1 flat table
        _STD fill(_STD begin(_Table), _STD end(_Table), _Pat_size);
        for (_Diff _Idx = 1; _Idx <= _Pat_size; ++_Idx, (void) ++_UPat_first) {
            _Table[_Unsigned_value(*_UPat_first)] = _Pat_size - _Idx;
        }
    }

    _Diff _Lookup(const _Value_t _Value) const { // lookup the "character" _Value in the table
        const auto _UValue = _Unsigned_value(_Value);
        if (_UValue < _STD size(_Table)) {
            return _Table[_UValue];
        }

        return _Pat_size;
    }

    equal_to<> _Get_eq() const { // return an equality comparer
        return {};
    }

    const _RanItPat _Pat_first;
    const _Diff _Pat_size;

private:
    _Diff _Table[_Limit];
};


// FUNCTION TEMPLATE _Build_boyer_moore_delta_2_table
template <class _RanItPat, class _Pred_eq>
inline void _Build_boyer_moore_delta_2_table(_Iter_diff_t<_RanItPat>* _Shifts, const _RanItPat _Pat_first,
    const _Iter_diff_t<_RanItPat> _Pat_size,
    _Pred_eq& _Eq) { // builds Boyer-Moore's delta_2 table from a pattern [_Pat_first, _Pat_first + _Pat_size)
                     // pre: _Shifts is a pointer to _Pat_size _Iter_diff_t<_RanIt>s
    if (_Pat_size == 0) {
        return;
    }

    using _Diff = _Iter_diff_t<_RanItPat>;
    unique_ptr<_Diff[]> _Suffix_fn{::new _Diff[static_cast<size_t>(_Pat_size)]};
    for (_Diff _Idx = 0; _Idx < _Pat_size; ++_Idx) {
        _Shifts[_Idx] = 2 * _Pat_size - _Idx - 1;
    }

    _Diff _Suffix = _Pat_size;
    for (_Diff _Idx = _Pat_size; _Idx > 0; --_Idx, (void) --_Suffix) {
        _Suffix_fn[static_cast<size_t>(_Idx - 1)] = _Suffix;
        while (_Suffix < _Pat_size && !_Eq(_Pat_first[_Idx - 1], _Pat_first[_Suffix])) {
            _Shifts[_Suffix] = _Min_value(_Shifts[_Suffix], _Pat_size - _Idx);
            _Suffix          = _Suffix_fn[static_cast<size_t>(_Suffix)];
        }
    }

    for (_Diff _Idx = 0; _Idx <= _Suffix; ++_Idx) {
        _Shifts[_Idx] = _Min_value(_Shifts[_Idx], _Pat_size + _Suffix - _Idx);
    }
}


// FUNCTION TEMPLATE _Boyer_moore_search
template <class _Delta1_t, class _RanItHaystack>
inline pair<_RanItHaystack, _RanItHaystack> _Boyer_moore_search(const _Delta1_t& _Delta1,
    typename _Delta1_t::_Diff* _Delta2, _RanItHaystack _First,
    _RanItHaystack _Last) { // run the loop of the Boyer-Moore string search algorithm
    static_assert(is_same_v<typename _Delta1_t::_Value_t, _Iter_value_t<_RanItHaystack>>,
        "boyer_moore_searcher requires matching iterator value types");
    using _Diff = typename _Delta1_t::_Diff;
    _Adl_verify_range(_First, _Last);
    auto _UFirst         = _Get_unwrapped(_First);
    const auto _ULast    = _Get_unwrapped(_Last);
    const auto _Pat_size = _Delta1._Pat_size;
    if (_Pat_size == 0) {
        return {_First, _First};
    }

    const auto _UPat_first = _Get_unwrapped_n(_Delta1._Pat_first, _Pat_size);
    const auto _Eq         = _Delta1._Get_eq();
    _Diff _Shift           = _Pat_size - 1;
    while (_Shift < _ULast - _UFirst) {
        _UFirst += _Shift;
        _Shift = _Delta1._Lookup(*_UFirst);
        if (_Shift == 0) { // that is, *_UFirst == "_Pat.back()"
            _Diff _Idx = _Pat_size - 1;
            do {
                if (_Idx == 0) {
                    _Seek_wrapped(_Last, _UFirst + _Pat_size);
                    _Seek_wrapped(_First, _UFirst);
                    return {_First, _Last};
                }

                --_Idx;
                --_UFirst;
            } while (_Eq(*_UFirst, _UPat_first[_Idx]));
            _Shift = _Max_value(_Delta1._Lookup(*_UFirst), _Delta2[_Idx]);
        }
    }

    _Seek_wrapped(_Last, _ULast);
    _Seek_wrapped(_First, _ULast);
    return {_First, _Last};
}


// FUNCTION TEMPLATE _Boyer_moore_horspool_search
template <class _Delta1_t, class _RanItHaystack>
inline pair<_RanItHaystack, _RanItHaystack> _Boyer_moore_horspool_search(const _Delta1_t& _Delta1,
    _RanItHaystack _First, _RanItHaystack _Last) { // run the loop of the Boyer-Moore-Horspool string search algorithm
    static_assert(is_same_v<typename _Delta1_t::_Value_t, _Iter_value_t<_RanItHaystack>>,
        "boyer_moore_horspool_searcher requires matching iterator value types");
    using _Diff = typename _Delta1_t::_Diff;
    _Adl_verify_range(_First, _Last);
    const auto _Pat_size = _Delta1._Pat_size;
    if (_Pat_size == 0) {
        return {_First, _First};
    }

    auto _UFirst           = _Get_unwrapped(_First);
    const auto _ULast      = _Get_unwrapped(_Last);
    const auto _UPat_first = _Get_unwrapped_n(_Delta1._Pat_first, _Pat_size);
    const auto _Eq         = _Delta1._Get_eq();
    _Diff _Shift           = _Pat_size - 1;
    while (_Shift < _ULast - _UFirst) {
        _UFirst += _Shift;
        _Shift = _Delta1._Lookup(*_UFirst);
        if (_Shift == 0) { // that is, *_UFirst == "_Pat.back()"
            const auto _Candidate = _UFirst - (_Pat_size - 1);
            if (_STD equal(_UPat_first, _UPat_first + (_Pat_size - 1), _Candidate, _Pass_fn(_Eq))) {
                _Seek_wrapped(_Last, _Candidate + _Pat_size);
                _Seek_wrapped(_First, _Candidate);
                return {_First, _Last};
            }

            _Shift = 1;
        }
    }

    _Seek_wrapped(_Last, _ULast);
    _Seek_wrapped(_First, _ULast);
    return {_First, _Last};
}


// STRUCT AND ALIAS TEMPLATES _Boyer_moore_traits
template <class _RanItPat, class _Hash_ty, class _Pred_eq, class _Delta1_t>
struct _Single_delta1_type_boyer_moore_traits {
    using _Diff = _Iter_diff_t<_RanItPat>;

    // uses buffers of the form {
    // _Atomic_counter_t _Ref_count
    // _Delta1_t _Delta1
    // _Diff _Delta2[_Pattern_size] // not used for Boyer-Moore-Horspool
    // }

    template <bool _Build_delta2>
    static void* _Build_boyer_moore(_RanItPat _First, _RanItPat _Last, _Hash_ty _Hash_fn,
        _Pred_eq _Eq) { // builds data tables for the Boyer-Moore string search algorithm
        _Adl_verify_range(_First, _Last);
        const auto _UFirst       = _Get_unwrapped(_First);
        const auto _Pat_size_raw = _Get_unwrapped(_Last) - _UFirst;
        using _CT                = common_type_t<_Iter_diff_t<_RanItPat>, size_t>;
        if (static_cast<_CT>(_Pat_size_raw) > static_cast<_CT>(SIZE_MAX)) {
            _Xbad_alloc();
        }

        const auto _Pat_size = static_cast<size_t>(_Pat_size_raw);
        size_t _Buf_size     = 0;
        _Add_alloc_size<_Atomic_counter_t>(_Buf_size);
        _Add_alloc_size<_Delta1_t>(_Buf_size);
        if (_Build_delta2) {
            _Add_alloc_size<_Diff>(_Buf_size, _Pat_size);
        }

        unique_ptr<void, _Global_delete> _Buf_bytes(::operator new(_Buf_size));
        void* _Buf                                      = _Buf_bytes.get();
        *_Decode_aligned_block<_Atomic_counter_t>(_Buf) = 1;
        void* const _Delta1                             = _Decode_aligned_block<_Delta1_t>(_Buf);
        if (_Build_delta2) {
            _Build_boyer_moore_delta_2_table(
                _Decode_aligned_block<_Diff>(_Buf, _Pat_size), _UFirst, _Pat_size_raw, _Eq);
        }

        ::new (_Delta1) _Delta1_t(_First, _UFirst, _Pat_size_raw, _STD move(_Hash_fn), _STD move(_Eq));
        return _Buf_bytes.release();
    }

    template <class _RanItHaystack>
    static pair<_RanItHaystack, _RanItHaystack> _Use_boyer_moore(void* _Data, _RanItHaystack _First,
        _RanItHaystack _Last) { // decodes data tables for the Boyer-Moore string search algorithm
        (void) _Decode_aligned_block<_Atomic_counter_t>(_Data);
        const auto _Delta1 = _Decode_aligned_block<_Delta1_t>(_Data);
        const auto _Delta2 = _Decode_aligned_block<_Diff>(_Data, static_cast<size_t>(_Delta1->_Pat_size));
        return _Boyer_moore_search(*_Delta1, _Delta2, _First, _Last);
    }

    template <class _RanItHaystack>
    static pair<_RanItHaystack, _RanItHaystack> _Use_boyer_moore_horspool(void* _Data, _RanItHaystack _First,
        _RanItHaystack _Last) { // decodes data tables for the Boyer-Moore string search algorithm
        (void) _Decode_aligned_block<_Atomic_counter_t>(_Data);
        const auto _Delta1 = _Decode_aligned_block<_Delta1_t>(_Data);
        return _Boyer_moore_horspool_search(*_Delta1, _First, _Last);
    }

    static void _Destroy(void* const _Base) noexcept { // destroys data tables for either the Boyer-Moore or
                                                       // Boyer-Moore-Horspool string search algorithms
        void* _Data = _Base;
        (void) _Decode_aligned_block<_Atomic_counter_t>(_Data);
        _Decode_aligned_block<_Delta1_t>(_Data)->~_Delta1_t();
        ::operator delete(_Base);
    }
};

template <class _RanItPat, class _Hash_ty, class _Pred_eq>
using _Boyer_moore_traits_char_mode = _Single_delta1_type_boyer_moore_traits<_RanItPat, _Hash_ty, _Pred_eq,
    _Boyer_moore_flat_delta_1_table<_RanItPat, 256>>;

template <class _RanItPat>
struct _Boyer_moore_traits_wchar_t_mode {
    using _Value_t       = _Iter_value_t<_RanItPat>;
    using _Diff          = _Iter_diff_t<_RanItPat>;
    using _Big_table_t   = _Boyer_moore_flat_delta_1_table<_RanItPat, 65536>;
    using _Small_table_t = _Boyer_moore_flat_delta_1_table<_RanItPat, 256>;

    // uses buffers of the form {
    // _Atomic_counter_t _Ref_count
    // bool _Use_large_table // true if anything in the pattern is > 255
    // conditional_t<_Use_large_table, _Big_table_t, _Small_table_t> _Delta1
    // _Diff _Delta2[_Pattern_size] // not used for Boyer-Moore-Horspool
    // }

    template <bool _Build_delta2>
    static void* _Build_boyer_moore(_RanItPat _First, _RanItPat _Last, _Unused_parameter,
        _Unused_parameter) { // builds data tables for the Boyer-Moore string search algorithm
        _Adl_verify_range(_First, _Last);
        const auto _UFirst       = _Get_unwrapped(_First);
        const auto _ULast        = _Get_unwrapped(_Last);
        const auto _Pat_size_raw = _ULast - _UFirst;
        using _CT                = common_type_t<_Iter_diff_t<_RanItPat>, size_t>;
        if (static_cast<_CT>(_Pat_size_raw) > static_cast<_CT>(SIZE_MAX)) {
            _Xbad_alloc();
        }

        const auto _Pat_size = static_cast<size_t>(_Pat_size_raw);
        size_t _Buf_size     = 0;
        _Add_alloc_size<_Atomic_counter_t>(_Buf_size);
        bool _Use_large_table = false;

        for (auto _Temp = _UFirst; _Temp != _ULast; ++_Temp) {
            if (_Unsigned_value(*_Temp) > 255) {
                _Use_large_table = true;
                break;
            }
        }

        _Add_alloc_size<bool>(_Buf_size);
        if (_Use_large_table) {
            _Add_alloc_size<_Big_table_t>(_Buf_size);
        } else {
            _Add_alloc_size<_Small_table_t>(_Buf_size);
        }

        if (_Build_delta2) {
            _Add_alloc_size<_Diff>(_Buf_size, _Pat_size);
        }

        unique_ptr<void, _Global_delete> _Buf_bytes(::operator new(_Buf_size));
        void* _Buf                                      = _Buf_bytes.get();
        *_Decode_aligned_block<_Atomic_counter_t>(_Buf) = 1;
        *_Decode_aligned_block<bool>(_Buf)              = _Use_large_table;
        if (_Use_large_table) {
            using _Delta1_t = _Big_table_t;
            ::new (static_cast<void*>(_Decode_aligned_block<_Delta1_t>(_Buf)))
                _Delta1_t(_First, _UFirst, _Pat_size_raw, {}, {});
        } else {
            using _Delta1_t = _Small_table_t;
            ::new (static_cast<void*>(_Decode_aligned_block<_Delta1_t>(_Buf)))
                _Delta1_t(_First, _UFirst, _Pat_size_raw, {}, {});
        }

        if (_Build_delta2) {
            equal_to<> _Eq;
            _Build_boyer_moore_delta_2_table(
                _Decode_aligned_block<_Diff>(_Buf, _Pat_size), _UFirst, _Pat_size_raw, _Eq);
        }

        return _Buf_bytes.release();
    }

    template <class _RanItHaystack>
    static pair<_RanItHaystack, _RanItHaystack> _Use_boyer_moore(void* _Data, _RanItHaystack _First,
        _RanItHaystack _Last) { // decodes data tables for the Boyer-Moore string search algorithm
        (void) _Decode_aligned_block<_Atomic_counter_t>(_Data);
        if (*_Decode_aligned_block<bool>(_Data)) {
            const auto _Delta1 = _Decode_aligned_block<_Big_table_t>(_Data);
            const auto _Delta2 = _Decode_aligned_block<_Diff>(_Data, static_cast<size_t>(_Delta1->_Pat_size));
            return _Boyer_moore_search(*_Delta1, _Delta2, _First, _Last);
        } else {
            const auto _Delta1 = _Decode_aligned_block<_Small_table_t>(_Data);
            const auto _Delta2 = _Decode_aligned_block<_Diff>(_Data, static_cast<size_t>(_Delta1->_Pat_size));
            return _Boyer_moore_search(*_Delta1, _Delta2, _First, _Last);
        }
    }

    template <class _RanItHaystack>
    static pair<_RanItHaystack, _RanItHaystack> _Use_boyer_moore_horspool(void* _Data, _RanItHaystack _First,
        _RanItHaystack _Last) { // decodes data tables for the Boyer-Moore string search algorithm
        (void) _Decode_aligned_block<_Atomic_counter_t>(_Data);
        if (*_Decode_aligned_block<bool>(_Data)) {
            const auto _Delta1 = _Decode_aligned_block<_Big_table_t>(_Data);
            return _Boyer_moore_horspool_search(*_Delta1, _First, _Last);
        } else {
            const auto _Delta1 = _Decode_aligned_block<_Small_table_t>(_Data);
            return _Boyer_moore_horspool_search(*_Delta1, _First, _Last);
        }
    }

    static void _Destroy(void* const _Base) noexcept { // destroys data tables for either the Boyer-Moore or
                                                       // Boyer-Moore-Horspool string search algorithms
        void* _Data = _Base;
        (void) _Decode_aligned_block<_Atomic_counter_t>(_Data);
        if (*_Decode_aligned_block<bool>(_Data)) {
            const auto _Delta1 = _Decode_aligned_block<_Big_table_t>(_Data);
            _Delta1->~_Big_table_t();
        } else {
            const auto _Delta1 = _Decode_aligned_block<_Small_table_t>(_Data);
            _Delta1->~_Small_table_t();
        }
        static_assert(is_trivially_destructible_v<_Diff>, "allows Boyer-Moore and Boyer-Moore-Horspool to "
                                                          "share cleanup functions");
        ::operator delete(_Base);
    }
};

template <class _RanItPat, class _Hash_ty, class _Pred_eq>
using _Boyer_moore_traits_general_mode = _Single_delta1_type_boyer_moore_traits<_RanItPat, _Hash_ty, _Pred_eq,
    _Boyer_moore_hash_delta_1_table<_RanItPat, _Hash_ty, _Pred_eq>>;

template <class _RanItPat, class _Hash_ty, class _Pred_eq, class _Value_t = _Iter_value_t<_RanItPat>>
using _Boyer_moore_traits =
    conditional_t<is_integral_v<_Value_t> && sizeof(_Value_t) <= 2
                      && (is_same_v<equal_to<>, _Pred_eq> || is_same_v<equal_to<_Value_t>, _Pred_eq>),
        conditional_t<sizeof(_Value_t) == 1, _Boyer_moore_traits_char_mode<_RanItPat, _Hash_ty, _Pred_eq>,
            _Boyer_moore_traits_wchar_t_mode<_RanItPat>>,
        _Boyer_moore_traits_general_mode<_RanItPat, _Hash_ty, _Pred_eq>>;


// CLASS TEMPLATE boyer_moore_searcher
template <class _RanItPat, class _Hash_ty = hash<_Iter_value_t<_RanItPat>>,
    class _Pred_eq = equal_to<>>
class boyer_moore_searcher { // an implementation of the Boyer-Moore string search algorithm
public:
    boyer_moore_searcher(
        const _RanItPat _First, const _RanItPat _Last, _Hash_ty _Hash_fn = _Hash_ty(), _Pred_eq _Eq = _Pred_eq())
        : _Data(_Traits::template _Build_boyer_moore<true>(_First, _Last, _STD move(_Hash_fn),
              _STD move(_Eq))) { // preprocess a pattern for use with the Boyer-Moore string search algorithm
    }

    boyer_moore_searcher(const boyer_moore_searcher& _Other) noexcept // strengthened
        : _Data(_Other._Data) { // copy an instance of the Boyer-Moore string search algorithm
        _MT_INCR(*static_cast<_Atomic_counter_t*>(_Data));
    }

    ~boyer_moore_searcher() noexcept { // destroy this instance
        if (_MT_DECR(*static_cast<_Atomic_counter_t*>(_Data)) == 0) {
            _Traits::_Destroy(_Data);
        }
    }

    boyer_moore_searcher& operator=(const boyer_moore_searcher& _Other) noexcept { // strengthened
        // assign over this instance
        boyer_moore_searcher _Cpy(_Other);
        swap(_Data, _Cpy._Data);
        return *this;
    }

    template <class _RanItHaystack>
    _NODISCARD pair<_RanItHaystack, _RanItHaystack> operator()(const _RanItHaystack _First,
        const _RanItHaystack _Last) const { // search for the preprocessed pattern in [_First, _Last)
        return _Traits::_Use_boyer_moore(_Data, _First, _Last);
    }

private:
    using _Traits = _Boyer_moore_traits<_RanItPat, _Hash_ty, _Pred_eq>;
    void* _Data;
};


// CLASS TEMPLATE boyer_moore_horspool_searcher
template <class _RanItPat, class _Hash_ty = hash<_Iter_value_t<_RanItPat>>,
    class _Pred_eq = equal_to<>>
class boyer_moore_horspool_searcher { // an implementation of the Boyer-Moore-Horspool string search algorithm
                                      // (equivalent to Boyer-Moore without the second table)
public:
    boyer_moore_horspool_searcher(
        const _RanItPat _First, const _RanItPat _Last, _Hash_ty _Hash_fn = _Hash_ty(), _Pred_eq _Eq = _Pred_eq())
        : _Data(_Traits::template _Build_boyer_moore<false>(_First, _Last, _STD move(_Hash_fn),
              _STD move(_Eq))) { // preprocess a pattern for use with the Boyer-Moore-Horspool string search algorithm
    }

    boyer_moore_horspool_searcher(const boyer_moore_horspool_searcher& _Other) noexcept // strengthened
        : _Data(_Other._Data) { // copy an instance of the Boyer-Moore-Horspool string search algorithm
        _MT_INCR(*static_cast<_Atomic_counter_t*>(_Data));
    }

    ~boyer_moore_horspool_searcher() noexcept {
        if (_MT_DECR(*static_cast<_Atomic_counter_t*>(_Data)) == 0) {
            _Traits::_Destroy(_Data);
        }
    }

    boyer_moore_horspool_searcher& operator=(const boyer_moore_horspool_searcher& _Other) noexcept { // strengthened
        // assign over this instance
        boyer_moore_horspool_searcher _Cpy(_Other);
        swap(_Data, _Cpy._Data);
        return *this;
    }

    template <class _RanItHaystack>
    _NODISCARD pair<_RanItHaystack, _RanItHaystack> operator()(const _RanItHaystack _First,
        const _RanItHaystack _Last) const { // search for the preprocessed pattern in [_First, _Last)
        return _Traits::_Use_boyer_moore_horspool(_Data, _First, _Last);
    }

private:
    using _Traits = _Boyer_moore_traits<_RanItPat, _Hash_ty, _Pred_eq>;
    void* _Data;
};
#endif // _HAS_CXX17

#if _HAS_TR1_NAMESPACE
namespace _DEPRECATE_TR1_NAMESPACE tr1 {
    using _STD bad_function_call;
    using _STD bind;
    using _STD function;
    using _STD is_bind_expression;
    using _STD is_placeholder;
    using _STD mem_fn;
    using _STD swap;
    namespace placeholders {
        using namespace _STD placeholders;
    }
} // namespace tr1
#endif // _HAS_TR1_NAMESPACE

_STD_END

#pragma pop_macro("new")
_STL_RESTORE_CLANG_WARNINGS
#pragma warning(pop)
#pragma pack(pop)
#endif // RC_INVOKED
#endif // _FUNCTIONAL_

/*
 * Copyright (c) by P.J. Plauger. All rights reserved.
 * Consult your license regarding permissions and restrictions.
V6.50:0009 */
